package com.zjsru.leetcode75.level1;

import java.util.Arrays;

/**
 * @Author: cookLee
 * @Date: 2023-11-22
 * 比特位计数
 */
public class CountBits {

    /**
     * 主
     * \
     * 输入：n = 2
     * 输出：[0,1,1]
     * 解释：
     * 0 --> 0
     * 1 --> 1
     * 2 --> 10
     * \
     * 输入：n = 5
     * 输出：[0,1,1,2,1,2]
     * 解释：
     * 0 --> 0
     * 1 --> 1
     * 2 --> 10
     * 3 --> 11
     * 4 --> 100
     * 5 --> 101
     * \
     * @param args
     */
    public static void main(String[] args) {
        CountBits countBits = new CountBits();
        int n = 2;
        System.out.println(Arrays.toString(countBits.countBits(n)));
    }

    /**
     * 计数位:模拟
     *
     * @param n n
     * @return {@link int[]}
     */
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            //可以使用API
            //int i = Integer.bitCount(i);
            int count = this.helper(i);
            ans[i] = count;
        }

        return ans;
    }

    /**
     * 计算位数助手类
     *
     * @param i
     * @return int
     */
    private int helper(int i) {
        int cnt = 0;
        while (i > 0) {
            i &= (i - 1);
            cnt++;
        }
        return cnt;
    }

    /**
     * 模拟
     *
     * @param num num
     * @return {@link int[]}
     */
    public int[] countBits2(int num) {
        int[] ans = new int[num + 1];
        ans[0] = 0;
        for (int i = 1; i <= num; i++) {
            //奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。
            if (i % 2 == 1) {
                ans[i] = ans[i - 1] + 1;
            } else {
                //偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。
                ans[i] = ans[i / 2];
            }
        }
        return ans;
    }

}
